home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 April: Mac OS SDK / Dev.CD Apr 96 SDK / Dev.CD Apr 96 SDK1.toast / Development Kits (Disc 1) / OpenDoc Development Framework / ODFDev / ODF / Found / FWCollec / Sources / FWNode.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1995-11-08  |  15.3 KB  |  614 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        FW_CPrivFWNode.cpp
  3.  
  4.     Contains:    Implementation of FW_CPrivNode class
  5.  
  6.     Written by:    Richard Rodseth
  7.  
  8.     Copyright:    © 1993 by Apple Computer, Inc., all rights reserved.
  9.  
  10.     Change History (most recent first):
  11.  
  12.          <4>    10/24/94    jpa        Added _Cast. Export fns on !ODDebug to keep
  13.                                     linker happy. [1188344]
  14.          <3>     9/29/94    RA        1189812: Mods for 68K build.
  15.          <2>      6/9/94    RR        Remove ASLM Stuff.
  16.          <2>     3/15/94    MB        Changes to support SCpp/ASLM builds,
  17.                                     #1150864.
  18.          <6>      2/7/94    JA        Tiger Team Makeover!
  19.          <5>     1/31/94    JA        Syntactic tweaks to deal with changes in
  20.                                     FW_CPrivLink and FW_CPrivLinkedList API.
  21.          <4>    11/12/93    JBS        fix SkipChildren()
  22.          <3>      9/3/93    JBS        added SkipChildren()
  23.          <2>     7/21/93    NP        Added outline destructor to FW_CPrivNode for ASLM.
  24.          <1>     1/26/93    RCR        first checked in
  25.  
  26.     To Do:
  27.         Optimization: Many methods could be inlined for speed & code size improvements.
  28. */
  29.  
  30. #include "FWFound.hpp"
  31.  
  32. #ifndef FWNODE_H
  33. #include "FWNode.h"
  34. #endif
  35.  
  36. #ifndef FWDEBUG_H
  37. #include "FWDebug.h"
  38. #endif
  39.  
  40. #if FW_LIB_EXPORT_PRAGMAS
  41. #pragma lib_export on
  42. #endif
  43.  
  44. #ifdef FW_BUILD_MAC
  45. #pragma segment fwcollec
  46. #endif
  47.  
  48. //======================================================================================
  49. // Class FW_CPrivNode
  50. //======================================================================================
  51.  
  52. //------------------------------------------------------------------------------
  53. // FW_CPrivNode::FW_CPrivNode
  54. //
  55. // Description
  56. //------------------------------------------------------------------------------
  57.  
  58. FW_CPrivNode::FW_CPrivNode() 
  59. {
  60.     fParent = NULL; 
  61. }
  62.  
  63. //------------------------------------------------------------------------------
  64. // FW_CPrivNode::~FW_CPrivNode
  65. //
  66. // Description
  67. //------------------------------------------------------------------------------
  68.  
  69. FW_CPrivNode::~FW_CPrivNode() 
  70. {
  71. }
  72.  
  73. //------------------------------------------------------------------------------
  74. // FW_CPrivNode::FW_CPrivNode
  75. //
  76. // Description
  77. //------------------------------------------------------------------------------
  78.  
  79. unsigned long FW_CPrivNode::Size() 
  80. {
  81.     unsigned long size = 0;
  82.     
  83.     FW_CPrivNode* node = this->FirstTopDown();
  84.     while (node)
  85.     {
  86.         size++;
  87.         node = node->NextTopDown(FW_kFrontToBack);
  88.     }
  89.     return size;
  90. }
  91.  
  92. //------------------------------------------------------------------------------
  93. // FW_CPrivNode::FW_CPrivNode
  94. //
  95. // Description
  96. //------------------------------------------------------------------------------
  97.  
  98. FW_CPrivNode* FW_CPrivNode::GetParent()
  99. {
  100.     return fParent;
  101. }
  102.  
  103. //------------------------------------------------------------------------------
  104. // FW_CPrivNode::FW_CPrivNode
  105. //
  106. // Description
  107. //------------------------------------------------------------------------------
  108.  
  109. FW_CPrivNode* FW_CPrivNode::GetFirstChild()
  110. {
  111.     return (FW_CPrivNode*) this->First();
  112. }
  113.  
  114. //------------------------------------------------------------------------------
  115. // FW_CPrivNode::FW_CPrivNode
  116. //
  117. // Description
  118. //------------------------------------------------------------------------------
  119.  
  120. FW_CPrivNode* FW_CPrivNode::GetLastChild()
  121. {
  122.     return (FW_CPrivNode*) this->Last();
  123. }
  124.  
  125. //------------------------------------------------------------------------------
  126. // FW_CPrivNode::FW_CPrivNode
  127. //
  128. // Description
  129. //------------------------------------------------------------------------------
  130.  
  131. FW_CPrivNode* FW_CPrivNode::GetNextSibling()
  132. {
  133.     FW_CPrivNode* parent = this->GetParent();
  134.     return parent ? parent->GetChildAfter(this) : NULL;
  135. }
  136.  
  137. //------------------------------------------------------------------------------
  138. // FW_CPrivNode::FW_CPrivNode
  139. //
  140. // Description
  141. //------------------------------------------------------------------------------
  142.  
  143. FW_CPrivNode* FW_CPrivNode::GetChildAfter(FW_CPrivNode* node)
  144. {
  145.     return (FW_CPrivNode*) this->After(*node);
  146. }
  147.  
  148. //------------------------------------------------------------------------------
  149. // FW_CPrivNode::FW_CPrivNode
  150. //
  151. // Description
  152. //------------------------------------------------------------------------------
  153.  
  154. FW_CPrivNode* FW_CPrivNode::GetChildBefore(FW_CPrivNode* node)
  155. {
  156.     return (FW_CPrivNode*) this->Before(*node);
  157. }
  158.  
  159. //------------------------------------------------------------------------------
  160. // FW_CPrivNode::FW_CPrivNode
  161. //
  162. // Description
  163. //------------------------------------------------------------------------------
  164.  
  165. FW_CPrivNode* FW_CPrivNode::GetPreviousSibling()
  166. {
  167.     FW_CPrivNode* parent = this->GetParent();
  168.     return parent ? parent->GetChildBefore(this) : NULL;
  169. }
  170.  
  171. //------------------------------------------------------------------------------
  172. // FW_CPrivNode::FW_CPrivNode
  173. //
  174. // Description
  175. //------------------------------------------------------------------------------
  176.  
  177. void FW_CPrivNode::SetParent(FW_CPrivNode* parent)
  178. {
  179.     fParent = parent;
  180. }
  181.  
  182. //------------------------------------------------------------------------------
  183. // FW_CPrivNode::FW_CPrivNode
  184. //
  185. // Description
  186. //------------------------------------------------------------------------------
  187.  
  188. void FW_CPrivNode::AddChildFirst(FW_CPrivNode* node)
  189. {
  190.     node->SetParent(this);
  191.     this->AddFirst(node);
  192. }
  193.  
  194. //------------------------------------------------------------------------------
  195. // FW_CPrivNode::FW_CPrivNode
  196. //
  197. // Description
  198. //------------------------------------------------------------------------------
  199.  
  200. void FW_CPrivNode::AddChildLast(FW_CPrivNode* node)
  201. {
  202.     node->SetParent(this);
  203.     this->AddLast(node);
  204. }
  205.  
  206. //------------------------------------------------------------------------------
  207. // FW_CPrivNode::FW_CPrivNode
  208. //
  209. // Description
  210. //------------------------------------------------------------------------------
  211.  
  212. void FW_CPrivNode::AddChildBefore(FW_CPrivNode& existing, FW_CPrivNode* node)
  213. {
  214.     node->SetParent(this);
  215.     this->FW_CPrivLinkedList::AddBefore(existing, node);
  216. }
  217.  
  218. //------------------------------------------------------------------------------
  219. // FW_CPrivNode::FW_CPrivNode
  220. //
  221. // Description
  222. //------------------------------------------------------------------------------
  223.  
  224. void FW_CPrivNode::AddChildAfter(FW_CPrivNode& existing, FW_CPrivNode* node)
  225. {
  226.     node->SetParent(this);
  227.     this->FW_CPrivLinkedList::AddAfter(existing, node);
  228. }
  229.  
  230. //------------------------------------------------------------------------------
  231. // FW_CPrivNode::FW_CPrivNode
  232. //
  233. // Description
  234. //------------------------------------------------------------------------------
  235.  
  236. void FW_CPrivNode::RemoveChild(FW_CPrivNode& child)
  237. {
  238.     this->FW_CPrivLinkedList::Remove(child);
  239. }
  240.  
  241. //------------------------------------------------------------------------------
  242. // FW_CPrivNode::FW_CPrivNode
  243. //
  244. // Description
  245. //------------------------------------------------------------------------------
  246.  
  247. FW_CPrivNode* FW_CPrivNode::FirstTopDown()
  248. {
  249.     return this;
  250. }
  251.  
  252. //------------------------------------------------------------------------------
  253. // FW_CPrivNode::FW_CPrivNode
  254. //
  255. // Description
  256. //------------------------------------------------------------------------------
  257.  
  258. FW_CPrivNode* FW_CPrivNode::NextTopDown(FW_SiblingOrder siblingOrder)
  259. {
  260.     FW_CPrivNode* child;
  261.     if (siblingOrder == FW_kFrontToBack)
  262.         child = this->GetFirstChild();
  263.     else
  264.         child = this->GetLastChild();
  265.     
  266.     if (child)
  267.         return child;
  268.     else 
  269.     {
  270.         FW_CPrivNode* sibling;
  271.         if (siblingOrder == FW_kFrontToBack)
  272.             sibling = this->GetNextSibling();
  273.         else 
  274.             sibling = this->GetPreviousSibling();
  275.  
  276.         if (sibling) 
  277.             return  sibling;
  278.         else 
  279.             return this->GetNextAunt(siblingOrder);
  280.     }
  281.     return NULL;
  282. }
  283.  
  284. //------------------------------------------------------------------------------
  285. // FW_CPrivNode::FW_CPrivNode
  286. //
  287. // Description
  288. //------------------------------------------------------------------------------
  289.  
  290. FW_CPrivNode* FW_CPrivNode::GetNextAunt(FW_SiblingOrder siblingOrder)
  291. {
  292.     FW_CPrivNode* parent = this->GetParent();
  293.     
  294.     if (parent)
  295.     {
  296.         FW_CPrivNode* sibling;
  297.         if (siblingOrder == FW_kFrontToBack)
  298.             sibling = parent->GetNextSibling();
  299.         else
  300.             sibling = parent->GetPreviousSibling();
  301.         
  302.         if (sibling) 
  303.             return sibling;
  304.         else 
  305.             return parent->GetNextAunt(siblingOrder);
  306.     }
  307.     else
  308.         return NULL;
  309. }
  310.  
  311. //------------------------------------------------------------------------------
  312. // FW_CPrivNode::FW_CPrivNode
  313. //
  314. // Description
  315. //------------------------------------------------------------------------------
  316.  
  317. FW_CPrivNode* FW_CPrivNode::FirstBottomUp(FW_SiblingOrder siblingOrder)
  318. {
  319.     FW_CPrivNode* child;
  320.     if (siblingOrder == FW_kFrontToBack)
  321.         child = this->GetFirstChild();
  322.     else
  323.         child = this->GetLastChild();
  324.  
  325.     if (child)
  326.         return child->FirstBottomUp(siblingOrder);
  327.     else
  328.         return this;
  329. }
  330.  
  331. //------------------------------------------------------------------------------
  332. // FW_CPrivNode::FW_CPrivNode
  333. //
  334. // Description
  335. //------------------------------------------------------------------------------
  336.  
  337. FW_CPrivNode* FW_CPrivNode::NextBottomUp(FW_SiblingOrder siblingOrder)
  338. {
  339.     FW_CPrivNode* parent = this->GetParent();
  340.  
  341.     if (parent)
  342.     {
  343.         FW_CPrivNode* sibling;
  344.         if (siblingOrder == FW_kFrontToBack)
  345.             sibling = parent->GetChildAfter(this);
  346.         else
  347.             sibling = parent->GetChildBefore(this);
  348.         
  349.         if (sibling)
  350.             return sibling->FirstBottomUp(siblingOrder);
  351.         else
  352.             return parent;
  353.     }
  354.     else
  355.         return NULL;    
  356.  
  357.     return NULL;
  358. }
  359.  
  360. //======================================================================================
  361. // FW_CPrivNodeTraverser
  362. //======================================================================================
  363.  
  364. //------------------------------------------------------------------------------
  365. // FW_CPrivNodeTraverser::FW_CPrivNodeTraverser
  366. //
  367. // Description
  368. //------------------------------------------------------------------------------
  369.  
  370. FW_CPrivNodeTraverser::FW_CPrivNodeTraverser(FW_CPrivNode* root, 
  371.                     FW_TraversalType traversalType, 
  372.                     FW_SiblingOrder siblingOrder)
  373. {
  374.     fRoot = root;
  375.     fCurrent = NULL;
  376.     fTraversalType = traversalType;
  377.     fSiblingOrder = siblingOrder;
  378. }
  379.  
  380. //------------------------------------------------------------------------------
  381. // FW_CPrivNodeTraverser::FW_CPrivNodeTraverser
  382. //
  383. // Description
  384. //------------------------------------------------------------------------------
  385.  
  386. FW_CPrivNodeTraverser::~FW_CPrivNodeTraverser()
  387. {
  388. }
  389.  
  390. //------------------------------------------------------------------------------
  391. // FW_CPrivNodeTraverser::FW_CPrivNodeTraverser
  392. //
  393. // Description
  394. //------------------------------------------------------------------------------
  395.  
  396. FW_CPrivNode*    FW_CPrivNodeTraverser::First()
  397. {
  398.     if (fRoot)
  399.     {
  400.         if (fTraversalType == FW_kTopDown)
  401.             fCurrent = this->FirstTopDown(fRoot);
  402.         else if (fTraversalType == FW_kBottomUp)
  403.             fCurrent = this->FirstBottomUp(fRoot,fSiblingOrder);
  404.         else if (fTraversalType == FW_kChildrenOnly)
  405.         {
  406.             if (fSiblingOrder == FW_kFrontToBack)
  407.                 fCurrent = fRoot->GetFirstChild();
  408.             else
  409.                 fCurrent = fRoot->GetLastChild();
  410.         }
  411.         return fCurrent;
  412.     }
  413.     else
  414.         return NULL;
  415. }
  416.  
  417. //------------------------------------------------------------------------------
  418. // FW_CPrivNodeTraverser::Next
  419. //
  420. // Description
  421. //------------------------------------------------------------------------------
  422.  
  423. FW_CPrivNode*    FW_CPrivNodeTraverser::Next()
  424. {
  425.     if (fCurrent)
  426.     {
  427.         if (fTraversalType == FW_kTopDown)
  428.             fCurrent = this->NextTopDown(fCurrent, fSiblingOrder);
  429.         else if (fTraversalType == FW_kBottomUp)
  430.             fCurrent = this->NextBottomUp(fCurrent, fSiblingOrder);
  431.         else if (fTraversalType == FW_kChildrenOnly)
  432.         {
  433.             if (fSiblingOrder == FW_kFrontToBack)
  434.                 fCurrent = fCurrent->GetNextSibling();
  435.             else
  436.                 fCurrent = fCurrent->GetPreviousSibling();
  437.         }
  438.         return fCurrent;
  439.     }
  440.     else
  441.         return NULL;
  442. }
  443.  
  444. //------------------------------------------------------------------------------
  445. // FW_CPrivNodeTraverser::SkipChildren
  446. //
  447. // Description
  448. //------------------------------------------------------------------------------
  449.  
  450. void FW_CPrivNodeTraverser::SkipChildren()
  451. {
  452.     FW_CPrivNode* next = NULL;
  453.     FW_CPrivNode* skipTo = NULL;
  454.     FW_CPrivNode* test = NULL;
  455.  
  456.     if (fCurrent)
  457.     {
  458.         if (fTraversalType == FW_kTopDown)
  459.         {
  460.             if (fSiblingOrder == FW_kFrontToBack)
  461.                 next = fCurrent->GetNextSibling();
  462.             else
  463.                 next = fCurrent->GetPreviousSibling();
  464.  
  465.             if (!next)
  466.                 next = fCurrent->GetNextAunt(fSiblingOrder);
  467.  
  468.             test = fCurrent;
  469.             while ( test != next )
  470.             {
  471.                 FW_ASSERT(test != NULL);
  472.                 skipTo = test;
  473.                 test = this->NextTopDown(test, fSiblingOrder);
  474.             }
  475.  
  476.             fCurrent = skipTo;
  477.         }
  478.     }
  479. }
  480.  
  481. //------------------------------------------------------------------------------
  482. // FW_CPrivNodeTraverser::IsNotComplete
  483. //
  484. // Description
  485. //------------------------------------------------------------------------------
  486.  
  487. FW_Boolean    FW_CPrivNodeTraverser::IsNotComplete()
  488. {
  489.     return (fCurrent != NULL);
  490. }
  491.  
  492. //------------------------------------------------------------------------------
  493. // FW_CPrivNodeTraverser::FirstTopDown
  494. //
  495. // Description
  496. //------------------------------------------------------------------------------
  497.  
  498. FW_CPrivNode* FW_CPrivNodeTraverser::FirstTopDown(FW_CPrivNode* node)
  499. {
  500.     return node;
  501. }
  502.  
  503. //------------------------------------------------------------------------------
  504. // FW_CPrivNodeTraverser::NextTopDown
  505. //
  506. // Description
  507. //------------------------------------------------------------------------------
  508.  
  509. FW_CPrivNode* FW_CPrivNodeTraverser::NextTopDown(FW_CPrivNode* node, FW_SiblingOrder siblingOrder)
  510. {
  511.     FW_CPrivNode* child;
  512.     if (siblingOrder == FW_kFrontToBack)
  513.         child = node->GetFirstChild();
  514.     else
  515.         child = node->GetLastChild();
  516.     
  517.     if (child)
  518.         return child;
  519.     else if (node != fRoot)
  520.     {
  521.         FW_CPrivNode* sibling;
  522.         if (siblingOrder == FW_kFrontToBack)
  523.             sibling = node->GetNextSibling();
  524.         else 
  525.             sibling = node->GetPreviousSibling();
  526.  
  527.         if (sibling) 
  528.             return  sibling;
  529.         else 
  530.             return this->GetNextAunt(node, siblingOrder);
  531.     }
  532.     return NULL;
  533. }
  534.  
  535. //------------------------------------------------------------------------------
  536. // FW_CPrivNodeTraverser::GetNextAunt
  537. //
  538. // Description
  539. //------------------------------------------------------------------------------
  540.  
  541. FW_CPrivNode* FW_CPrivNodeTraverser::GetNextAunt(FW_CPrivNode* node, FW_SiblingOrder siblingOrder)
  542. {
  543.     FW_CPrivNode* parent = node->GetParent();
  544.     
  545.     if (parent && (parent != fRoot))
  546.     {
  547.         FW_CPrivNode* sibling;
  548.         if (siblingOrder == FW_kFrontToBack)
  549.             sibling = parent->GetNextSibling();
  550.         else
  551.             sibling = parent->GetPreviousSibling();
  552.         
  553.         if (sibling) 
  554.             return sibling;
  555.         else 
  556.             return this->GetNextAunt(parent, siblingOrder);
  557.     }
  558.     else
  559.         return NULL;
  560. }
  561.  
  562. //------------------------------------------------------------------------------
  563. // FW_CPrivNodeTraverser::FirstBottomUp
  564. //
  565. // Description
  566. //------------------------------------------------------------------------------
  567.  
  568. FW_CPrivNode* FW_CPrivNodeTraverser::FirstBottomUp(FW_CPrivNode* node, FW_SiblingOrder siblingOrder)
  569. {
  570.     FW_CPrivNode* child;
  571.     if (siblingOrder == FW_kFrontToBack)
  572.         child = node->GetFirstChild();
  573.     else
  574.         child = node->GetLastChild();
  575.  
  576.     if (child)
  577.         return this->FirstBottomUp(child, siblingOrder);
  578.     else
  579.         return node;
  580. }
  581.  
  582. //------------------------------------------------------------------------------
  583. // FW_CPrivNode::FW_CPrivNode
  584. //
  585. // Description
  586. //------------------------------------------------------------------------------
  587.  
  588. FW_CPrivNode* FW_CPrivNodeTraverser::NextBottomUp(FW_CPrivNode* node, FW_SiblingOrder siblingOrder)
  589. {
  590.     if (node == fRoot)
  591.         return NULL;
  592.         
  593.     FW_CPrivNode* parent = node->GetParent();
  594.  
  595.     if (parent)
  596.     {
  597.         FW_CPrivNode* sibling;
  598.         if (siblingOrder == FW_kFrontToBack)
  599.             sibling = parent->GetChildAfter(node);
  600.         else
  601.             sibling = parent->GetChildBefore(node);
  602.         
  603.         if (sibling)
  604.             return this->FirstBottomUp(sibling, siblingOrder);
  605.         else
  606.             return parent;
  607.     }
  608.     else
  609.         return NULL;    
  610.  
  611.     return NULL;
  612. }
  613.  
  614.